typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType val;
}QNode;
typedef struct Queue
{
	QNode* head;//队头指针
	QNode* tail;//队尾指针
}Queue;
void QueueInit(Queue* pq);//队列初始化
void QueuePush(Queue* pq, QDataType x);//队尾插入数据
void QueuePop(Queue* pq);//队头删除数据
QDataType QueueBack(Queue* pq);//取队尾数据
QDataType QueueFront(Queue* pq);//取队头数据
int QueueSize(Queue* pq);//队列长度
bool QueueEmpty(Queue* pq);//队列判空
void QueueDestory(Queue* pq);//销毁队列
void QueueInit(Queue* pq)//队列初始化
{
	assert(pq);
	pq->head = pq->tail = NULL;
}
void QueuePush(Queue* pq, QDataType x)//队尾插入数据
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	newnode->val = x;
	newnode->next = NULL;
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	else
	{
		if (pq->head == NULL)
		{
			pq->head = pq->tail = newnode;
		}
		else
		{
			pq->tail->next = newnode;
			pq->tail = newnode;
		}
	}
}
void QueuePop(Queue* pq)//队头删除数据
{
	assert(pq);
	assert(pq->head);
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
	
}
QDataType QueueBack(Queue* pq)//取队尾数据
{
	assert(pq);
	assert(pq->head);
	return pq->tail->val;
}
QDataType QueueFront(Queue* pq)//取队头数据
{
	assert(pq);
	assert(pq->head);
	return pq->head->val;
}
int QueueSize(Queue* pq)//队列长度
{
	int size = 0;
	assert(pq);
	assert(pq->head);
	QNode* cur = pq->head;
	while (cur)
	{
		++size;
		cur = cur->next;
	}
	return size;
}
bool QueueEmpty(Queue* pq)//队列判空
{
	assert(pq);
	return pq->head == NULL;
}
void QueueDestory(Queue* pq)//销毁队列
{
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}

typedef struct {
    Queue q1;
    Queue q2;

} MyStack;


MyStack* myStackCreate() {
    MyStack* ps=(MyStack*)malloc(sizeof(MyStack));
    if(ps==NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }
   QueueInit(&(ps->q1));
   QueueInit(&(ps->q2));
   return ps;
}

void myStackPush(MyStack* obj, int x) {
   if(!QueueEmpty(&obj->q1))//往非空的队列入数据
   {
       QueuePush(&obj->q1,x);
   }
  else
  {
      QueuePush(&obj->q2,x);
  }
}

int myStackPop(MyStack* obj) {
  Queue* EmptyQ=&obj->q1;//默认q1为空，如果不是更改
  Queue* NoneEmptyQ=&obj->q2;//默认q1为空，如果不是更改
  if(!QueueEmpty(&obj->q1))//q2为空
  {
    EmptyQ=&obj->q2;
    NoneEmptyQ=&obj->q1;
  }
  //此时不用关注q1,q2谁具体为空
  //倒数据（非空往空里入，直到只剩一个）
  while(QueueSize(NoneEmptyQ)>1)
  {
      QueuePush(EmptyQ,QueueFront(NoneEmptyQ));
      QueuePop(NoneEmptyQ);
  }
  //出最后一个
  int top=QueueFront(NoneEmptyQ);
  QueuePop(NoneEmptyQ);
  return top;
}

int myStackTop(MyStack* obj) {
    if(!QueueEmpty(&obj->q1))//q1非空,取队尾
    {   
        return QueueBack(&obj->q1);
    }
   else
   {
    return QueueBack(&obj->q2);
   } 
}

bool myStackEmpty(MyStack* obj) {

return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);//两个都空才能结束
}
//要先释放内部的队列，才能释放外面的栈
void myStackFree(MyStack* obj) {

QueueDestory(&obj->q1);
QueueDestory(&obj->q2);
free(obj);
obj=NULL;

}